#include "data_structure/listo.h"
#include <stdlib.h>
#include <string.h>

struct ListO
{
    PListO_Node begin;
    PListO_Node end;
    bool (*equal)(PData_Val, PData_Val);
    bool (*less)(PData_Val, PData_Val);
    size_t list_size;
    size_t sizeof_type;
};

//创建并返回一个数据域大小为sizeof_type的节点
//创建失败返回NULL
static PListO_Node listO_node_creat(int sizeof_type);

//销毁一个节点
static void listO_node_destory(PListO_Node node);

//设置一个节点的内容
static void listO_node_set(PListO_Node node, CPData_Val data, int data_size);

//从链表中分离出指定节点
static PListO_Node listO_node_separate(PListO thisc, PListO_Node location);

//交换两个节点的位置
static void listO_node_swap(PListO_Node node_r, PListO_Node node_f);

//创建并返回一个数据域大小为sizeof_type的节点
//创建失败返回NULL
static PListO_Node listO_node_creat(int sizeof_type)
{
    PListO_Node new_node = (PListO_Node)malloc(sizeof(ListO_Node));
    if (new_node == NULL)
        return NULL;
    new_node->data = (PData_Val)malloc(sizeof_type);
    return new_node;
}

//销毁一个节点
static void listO_node_destory(PListO_Node node)
{
    free(node->data);
    free(node);
}

//连接连个节点
//将src连接到dest的后面
#define listO_node_link(dest, src) \
    {                              \
        if (dest && src)           \
        {                          \
            dest->next = src;      \
        }                          \
    }

//设置一个节点的内容
static void listO_node_set(PListO_Node node, CPData_Val data, int data_size)
{
    if (node && data && data_size > 0)
        memcpy(node->data, data, data_size);
}

//从链表中分离出指定节点
static PListO_Node listO_node_separate(PListO thisc, PListO_Node location)
{
    if (location == NULL || thisc == NULL)
        return NULL;

    if (thisc->begin == NULL)
        return NULL;

    if (location == thisc->begin)
    {
        PListO_Node p = thisc->begin;

        if (p->next != NULL)
        {
            thisc->begin = p->next;
            thisc->list_size--;
        }
        else
        {
            thisc->begin = thisc->end = NULL;
            thisc->list_size = 0;
        }
        return p;
    }

    if (location == thisc->end)
    {
        PListO_Node p = thisc->end;
        thisc->end->next = NULL;
        thisc->list_size--;
        return p;
    }

    PListO_Node p = thisc->begin;
    PListO_Node prev = p;

    while (p != location && p != NULL)
    {
        prev = p;
        p = p->next;
    }

    if (p == NULL)
        return NULL;

    if (prev && p->next)
    {
        listO_node_link(prev, p->next);
        thisc->list_size--;
        return p;
    }
    else
    {
        return NULL;
    }
}

//绑定用于比较两个元素的大小的函数
void listO_bind_equal(PListO thisc, bool (*equal)(PData_Val, PData_Val))
{
    thisc->equal = equal;
}

//绑定用于比较两个元素的大小的函数
void listO_bind_less(PListO thisc, bool (*less)(PData_Val, PData_Val))
{
    thisc->less = less;
}

PListO listO_creat(int sizeof_type)
{
    PListO thisc = (PListO)malloc(sizeof(ListO));
    thisc->begin = thisc->end = NULL;
    thisc->list_size = 0;
    thisc->sizeof_type = sizeof_type;
    return thisc;
}

//销毁链表
void listO_destory(PListO thisc)
{
    if (thisc == NULL)
        return 0;
    PListO_Node p = thisc->begin, prev;
    while (p)
    {
        free(p->data);
        prev = p;
        p = p->next;
        free(prev);
        thisc->list_size--;
    }
}

//返回指向容器中第一个元素的双向迭代器。
PListO_Node listO_begin(PListO thisc)
{
    return thisc->begin;
}

//返回指向容器中最后一个元素所在位置的双向迭代器。
PListO_Node listO_end(PListO thisc)
{
    return thisc->end;
}

//和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
CPListO_Node listO_cbegin(PListO thisc)
{
    return thisc->begin;
}

//和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
CPListO_Node listO_cend(PListO thisc)
{
    return thisc->end;
}

//判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
bool listO_empty(PListO thisc)
{
    return thisc->list_size;
}

//返回当前容器实际包含的元素个数。
size_t listO_size(PListO thisc)
{
    return thisc->list_size;
}

//返回第一个元素的引用。
CPData_Val listO_front(PListO thisc)
{
    if (thisc->begin != NULL)
        return thisc->begin->data;
    return NULL;
}

//返回最后一个元素的引用。
CPData_Val listO_back(PListO thisc)
{
    if (thisc->end != NULL)
        return thisc->end->data;
    return NULL;
}

//在容器头部插入一个元素。
void listO_push_front(PListO thisc, CPData_Val data)
{
    if (thisc->list_size == 0)
    {
        thisc->begin = listO_node_creat(thisc->sizeof_type);
        listO_node_set(thisc->begin, data, thisc->sizeof_type);
        thisc->end = thisc->begin;
        thisc->list_size = 1;
    }
    else
    {
        PListO_Node p = listO_node_creat(thisc->sizeof_type);
        listO_node_set(p, data, thisc->sizeof_type);
        listO_node_link(p, thisc->begin);
        thisc->begin = p;
        thisc->list_size++;
    }
}

//在容器尾部插入一个元素。
void listO_push_back(PListO thisc, CPData_Val data)
{
    if (thisc->list_size == 0)
    {
        thisc->end = listO_node_creat(thisc->sizeof_type);
        listO_node_set(thisc->end, data, thisc->sizeof_type);
        thisc->begin = thisc->end;
        thisc->list_size = 1;
    }
    else
    {
        PListO_Node p = listO_node_creat(thisc->sizeof_type);
        listO_node_set(p, data, thisc->sizeof_type);
        listO_node_link(thisc->end, p);
        p->next = NULL;
        thisc->end = p;
        thisc->list_size++;
    }
}

//删除容器头部的一个元素。
void listO_pop_front(PListO thisc)
{
    PListO_Node p = listO_node_separate(thisc, thisc->begin);
    if (p)
        listO_node_destory(p);
}

//删除容器尾部的一个元素。
void listO_pop_back(PListO thisc)
{
    PListO_Node p = listO_node_separate(thisc, thisc->end);
    if (p)
        listO_node_destory(p);
}

//在容器中的指定位置前插入元素。
void listO_insert(PListO thisc, PListO_Node location, CPData_Val data)
{
    if (location == thisc->begin)
    {
        listO_push_front(thisc, data);
        return;
    }

    if (location == NULL)
        return;

    PListO_Node prev, p = thisc->begin;
    while (p && p != location)
    {
        prev = p;
        p = p->next;
    }

    if (!p)
    {
        return NULL;
    }

    PListO_Node node = listO_node_creat(thisc->sizeof_type);
    listO_node_set(node, data, thisc->sizeof_type);
    listO_node_link(prev, node);
    listO_node_link(node, location);
    thisc->list_size++;
}

//删除容器中一个元素。
void listO_erase(PListO thisc, PListO_Node location)
{
    PListO_Node p = listO_node_separate(thisc, location);
    if (p)
        listO_node_destory(p);
}

//删除容器中某区域内的元素。
void listO_erase_as(PListO thisc, PListO_Node begin, PListO_Node end)
{
    if (begin != NULL && end != NULL)
    {
        PListO_Node p_begin = thisc->begin, prev_begin;
        //检查begin是否属于thisc
        while (p_begin != begin && p_begin != NULL)
        {
            prev_begin == p_begin;
            p_begin = p_begin->next;
        }

        if (p_begin == NULL || p_begin != begin)
            return;

        PListO_Node p_end = p_begin;
        //检查end是否属于thisc,且在begin之后
        while (p_end != end && p_end != NULL)
            p_end = p_end->next;

        if (p_end == NULL || p_end != end)
            return;

        PListO_Node p;
        if (prev_begin != NULL && end->next != NULL)
        {
            listO_node_link(prev_begin, end->next);
            for (p = begin, begin = begin->next; begin != end && begin != NULL; p = begin, begin = begin->next)
            {
                listO_node_destory(p);
                thisc->list_size--;
            }
        }
    }
}

//删除容器中所有等于 val 的元素。
//使用前应调用list_bind_equal()函数绑定比较函数
void listO_remove(PListO thisc, PData_Val val)
{
    PListO_Node p = thisc->begin, prev = NULL;
    while (p != NULL)
    {
        if (thisc->equal(p->data, val))
        {
            if (prev != NULL && p->next != NULL)
            {
                listO_node_link(prev, p->next);
                listO_node_destory(p);
                thisc->list_size--;
            }
            else if (prev != NULL)
                listO_pop_back(thisc);
            else
                listO_pop_front(thisc);
            thisc->list_size--;
        }
        prev = p;
        p = p->next;
    }
}

//删除容器中满足条件的元素。
void listO_remove_if(PListO thisc, bool (*factor)(PData_Val))
{
    PListO_Node p = thisc->begin, prev;
    while (p != NULL)
    {
        if (factor(p->data))
        {
            if (prev != NULL && p->next != NULL)
            {
                listO_node_link(prev, p->next);
                listO_node_destory(p);
                thisc->list_size--;
            }
            else if (prev != NULL)
                listO_pop_back(thisc);
            else
                listO_pop_front(thisc);
            thisc->list_size--;
        }
        prev = p;
        p = p->next;
    }
}

//删除容器中相邻的重复元素，只保留一个。
//使用前应调用list_bind_equal()函数绑定比较函数
void listO_unique(PListO thisc)
{
    PListO_Node p = thisc->begin, prev;
    while (p != NULL && p->next != NULL)
    {
        if (thisc->equal(p->data, p->next->data))
        {
            if (prev != NULL)
            {
                listO_node_link(prev, p->next);
                p = p->next;
                listO_node_destory(prev);
                thisc->list_size--;
            }
            else
            {
                p = p->next;
                listO_pop_front(thisc);
            }
            thisc->list_size--;
        }
        prev = p;
        p = p->next;
    }
}

//合并两个事先已排好序的 listO 容器，并且合并之后的 listO 容器依然是有序的。
//使用前应保证两个链表中有一个调用list_bind_less()函数绑定比较函数
PListO listO_merge(PListO listO_r, PListO listO_f)
{
    bool (*less)(PData_Val, PData_Val);
    if (listO_r == NULL || listO_f == NULL)
        return NULL;
    if (listO_r->less != NULL)
        less = listO_r->less;
    else if (listO_f->less != NULL)
        less = listO_f->less;
    else
        return NULL;

    PListO thisc = listO_Creat(listO_r->sizeof_type);
    PListO_Node p, pr, pf;
    pr = listO_r->begin;
    pf = listO_f->begin;
    while (pr && pf)
    {
        if (less(pr->data, pf->data))
        {
            p = pr;
            pr = pr->next;
            listO_node_separate(listO_r, p);
        }
        else
        {
            p = pf;
            pf = pf->next;
            listO_node_separate(listO_f, p);
        }
        if (thisc->list_size == 0)
        {
            thisc->begin = thisc->end = p;
            p->next = NULL;
            thisc->list_size = 1;
        }
        else
        {
            listO_node_link(thisc->end, p);
            p->next = NULL;
            thisc->list_size++;
        }
    }
    free(listO_r);
    free(listO_f);
    return thisc;
}

//通过更改容器中元素的位置，将它们进行排序。
//使用前应调用list_bind_less()函数绑定比较函数
void listO_sort(PListO thisc)
{
    PListO_Node begin = thisc->begin, p;
    while (begin != NULL)
    {
        while (p->next != NULL)
        {
            p = begin;
            if (thisc->less(p->next, p))
                p = p->next;
        }
        listO_node_swap(begin, p);
        begin = begin->next;
    }
}

// 反转容器中元素的顺序。
void listO_reverse1(PListO thisc)
{
    if (thisc == NULL)
        return;
    if (thisc->begin == NULL)
        return;

    PListO_Node begin, end, mid;
    end = thisc->begin;

    //如果只有一个节点，直接返回
    if (!end->next)
        return;

    end->next = NULL;
    thisc->end = end;

    //如果只有两个节点，调换begin 与 end
    mid = end->next;
    if (!mid->next)
    {
        thisc->begin = thisc->end;
        thisc->begin->next = end;
        return;
    }

    begin = mid->next;
    while (begin)
    {
        mid->next = end;
        end = mid;
        mid = begin;
        begin = begin->next;
    }

    thisc->begin = mid;
}